#include <vector>
#include <stack>
#include <queue>
using namespace std;

template <class T>
int partion1(vector<T>& vc, int left, int right){
  int keyi = left;
  while(left < right)
  {
    while(left < right && vc[right] >= vc[keyi])
    {
      --right;
    }
    while(left < right && vc[left] <= vc[keyi])
    {
      ++left;
    }
    swap(vc[left], vc[right]);
  }
  swap(vc[keyi], vc[left]);
  return left;
}

template <class T>
int partion2(vector<T>& vc, int left, int right){
  T key = vc[left];
  int piti = left;
  while(left < right)
  {
    while(left < right && vc[right] >= key)
    {
      --right;
    }
    vc[piti] = vc[right];
    piti = right;
    while(left < right && vc[left] <= key)
    {
      ++left;
    }
    vc[piti] = vc[left];
    piti = left;
  }
  vc[piti] = key;
  return piti;
}

template <class T>
int get_mid_index(vector<T>& vc, int left, int right){
  int mid = left+(right-left)/2;
  int tmp1 = vc[left] > vc[mid]? left : mid;
  int tmp2 = vc[right] > vc[mid]? right : mid;
  return vc[tmp1] > vc[tmp2]? tmp2 : tmp1;
}

template <class T>
int partion3(vector<T>& vc, int left, int right){
  int midi = get_mid_index(vc, left, right);
  swap(vc[midi], vc[left]);
  
  int prev = left;
  int cur = prev+1;
  int keyi = left;
  while(cur <= right)
  {
    if(vc[cur] < vc[keyi] && cur != ++prev)
    {
      swap(vc[prev], vc[cur]);
    }
    ++cur;
  }
  swap(vc[prev], vc[keyi]);
  return prev;
}

template <class T>
void insert_sort(vector<T>& vc, int start, int n){
  for(int i = start; i < start+n-1; ++i)
  {
    int end = i;
    T x = vc[end+1];
    while(end >= 0)
    {
      if(x < vc[end])
      {
        vc[end+1] = vc[end];
        --end;
      }
      else{
        break;
      }
    }
    vc[end+1] = x;
  }
}

unsigned count = 0;

template <class T>
void quick_sort(vector<T>& vc, int begin, int end){
  if(begin >= end)
  {
    ++count;
    return;
  }

  if(end-begin+1 <= 3)
  {
    insert_sort(vc, begin, end-begin+1); 
    return;
  }

  int div = partion3(vc, begin, end);
  quick_sort(vc, begin, div-1);
  quick_sort(vc, div+1, end);
}

//template <class T>
//void quick_sort(vector<T>& vc, int begin, int end){
//  if(end-begin+1 <= 3)
//  {
//    insert_sort(vc, begin, end-begin+1); 
//    return;
//  }
//
//  int div = partion3(vc, begin, end);
//  if(begin < div-1)
//  {
//    quick_sort(vc, begin, div-1);
//  }
//  if(div+1 < end)
//  {
//    quick_sort(vc, div+1, end);
//  }
//}

//template <class T>
//void quick_sort(vector<T>& vc, int begin, int end){
// stack<int> st;
// st.push(begin);
// st.push(end);
//
// while(!st.empty())
// {
//  end = st.top();
//  st.pop();
//  begin = st.top();
//  st.pop();
//  if(end-begin+1 < 15)
//  {
//    insert_sort(vc,begin,end-begin+1); 
//    continue;
//  }
//  int div = partion3(vc,begin,end);
//  if(begin < div-1)
//  {
//    st.push(begin);
//    st.push(div-1);
//  }
//  if(div+1 < end)
//  {
//    st.push(div+1);
//    st.push(end);
//  }
// }
//}

//template <class T>
//void quick_sort(vector<T>& vc, int begin, int end){
//  queue<int> que;
//  que.push(begin);
//  que.push(end);
//
//  while(!que.empty())
//  {
//    begin = que.front();
//    que.pop();
//    end = que.front();
//    que.pop();
//    if(end-begin+1 < 3)
//    {
//      insert_sort(vc,begin,end-begin+1); 
//      continue;
//    }
//    int div = partion3(vc,begin,end);
//    if(begin<div-1)
//    {
//      que.push(begin);
//      que.push(div-1);
//    }
//    if(div+1<end)
//    {
//      que.push(div+1);
//      que.push(end)
//    }
//  }
//}

